﻿using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;
using System.Threading.Tasks;

namespace Sort
{
    /*
        希尔(Shell)排序又称为缩小增量排序，它是一种插入排序。它是直接插入排序算法的一种威力加强版。
        该方法因DL．Shell于1959年提出而得名。
        希尔排序的基本思想是：
        把记录按步长 gap 分组，对每组记录采用直接插入排序方法进行排序。
        随着步长逐渐减小，所分成的组包含的记录越来越多，当步长的值减小到 1 时，整个数据合成为一组，构成一组有序记录，则完成排序。
     * 
     * 和直接插入排序比较：
        直接插入排序是稳定的；而希尔排序是不稳定的。
        直接插入排序更适合于原始记录基本有序的集合。
        希尔排序的比较次数和移动次数都要比直接插入排序少，当N越大时，效果越明显。   
        在希尔排序中，增量序列gap的取法必须满足：最后一个步长必须是 1 。 
        直接插入排序也适用于链式存储结构；希尔排序不适用于链式结构。
     */
    class ShellSort
    {
        static void Main()
        {
            Console.WriteLine("ShellSort");
            int[] arr = { 1, 2, 3, 5, 0, 9, 8, 7, 6, 4 };
            Sort(arr);
            Utils.WriteArr(arr);

            //Random rd = new Random();
            //for (int j = 0; j < 1000; j++)
            //{
            //    for (int i = 0; i < 10; i++)
            //    {
            //        arr[i] = rd.Next(20);
            //    }
            //    Sort(arr);
            //    if (!Utils.CheckOrderArray(arr))
            //    {
            //        Console.WriteLine("error.");
            //    }
            //    //Utils.WriteArr(arr);
            //}

            int size = 50000;
            int[] list = new int[size];
            Random rd = new Random();

            for (int j = 0; j < size; j++)
            {
                list[j] = rd.Next(100);
            }
            
            Utils.CheckRunTime(() =>
            {
                Sort(list);
            }, "sell sort ");


            int[] list1 = new int[size];
            Buffer.BlockCopy(list, 0, list1, 0, size);

            Utils.CheckRunTime(() =>
            {
                InsertSort.Sort(list1);
            }, "InsertSort sort ");

            if (!Utils.CheckOrderArray(list))
            {
                Console.WriteLine("error.");
            }
        }

        public static void Sort(int[] arr){
            int len = arr.Length;
            int gap = (len / 2);
            while (gap >= 1)
            {
                for(int i=0; i<gap; i++)
                {
                    InsertSort.Sort(arr, gap, i);
                }
                gap = gap / 2;
            }
        }
    }
}
